Prefix function

2023-02-24 22:04| 来源: 网络整理| 查看: 265

Last update: December 13, 2022 Translated From: e-maxx.ru Prefix function. Knuth鈥揗orris鈥揚ratt algorithm Prefix function definition

You are given a string $s$ of length $n$. The prefix function for this string is defined as an array $\pi$ of length $n$, where $\pi[i]$ is the length of the longest proper prefix of the substring $s[0 \dots i]$ which is also a suffix of this substring. A proper prefix of a string is a prefix that is not equal to the string itself. By definition, $\pi[0] = 0$.

Mathematically the definition of the prefix function can be written as follows:

$$\pi[i] = \max_ {k = 0 \dots i} \{k : s[0 \dots k-1] = s[i-(k-1) \dots i] \}$$

For example, prefix function of string "abcabcd" is $[0, 0, 0, 1, 2, 3, 0]$, and prefix function of string "aabaaab" is $[0, 1, 0, 1, 2, 2, 3]$.

Trivial Algorithm

An algorithm which follows the definition of prefix function exactly is the following:

vector prefix_function(string s) { int n = (int)s.length(); vector pi(n); for (int i = 0; i

【本文地址】

公司简介

联系我们